﻿//https://leetcode.cn/problems/4sum/description/
//第一次想法：left - fixleft - fixright - right
//由中间2个位置fixleft、fixright为固定位，left、right双指针寻找剩余2个数（++、--即可）
//一次固定位寻找完毕后，移动一个固定位即可，（fixleft--或fixright++），当固定位走完整个数组既找完
//注：由于[fixleft , fixright]之间的元素个数的变化，2个固定位不能单纯的依次取边界值，
//需要考虑排列组合，既[fixleft , fixright]中取2个数当作固定值，但是又由于当这个固定区间变大时，新的排列组合一定包含了之前的排列组合
//便造成了重复，需要排除 -》初步方法，只需要将新添加如的固定值依次与原固定区间的每个数结合即可
//由于上述方法过于麻烦QAQ，且不能重复利用基本的代码递归式编写（每次新的n数取和就要取新的指针与区间，不能标准化）
//还不如直接仿造三数取和的方法，递归式编写皆可，（三数取和：固定一个数，左右指针找剩下2个数）固定一个数找3个数
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int fixLeft, fixRight, left, right;
        left = 0, right = nums.size() - 1;
        //从中间开始向左右固定2个值，左右指针依次从头尾寻找寻找
        for (fixLeft = nums.size() / 2; fixLeft > 0;)
        {
            for (fixRight = nums.size() / 2 + 1; fixRight < nums.size() - 1;)
            {
                int fixtarget = target - (nums[fixLeft] + nums[fixRight]);
                left = 0, right = nums.size() - 1;
                while (left < fixLeft && right > fixRight)
                {
 cout << "left:" << left << " fixLeft:" << fixLeft << " left: " << left << " right:" << right << endl;

                    if (nums[left] + nums[right] < fixtarget)++left;
                    else if (nums[left] + nums[right] > fixtarget)--right;
                    else
                    {
                        ret.push_back({ nums[fixLeft],nums[fixRight],nums[left],nums[right] });
                        left++; right--;

                        //非固定指针去重
                        while (left < fixLeft && nums[left] == nums[left - 1])left++;
                        while (right > fixRight && nums[right] == nums[right + 1])right--;
                    }
                }
                //固定右指针去重
                ++fixRight;
                while (nums[fixRight] == nums[fixRight - 1])fixRight++;
            }
            //固定左指针去重
            --fixLeft;
            while (nums[fixLeft] == nums[fixLeft + 1])fixLeft--;
        }
        return ret;
    }
};

//借用三数取和的递归式写法
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        //固定一个数找剩余3个数
        for (int fixOne = 0; fixOne <= len - 4;)
        {

            //单次单固定的寻找
            for (int fixTwo = fixOne + 1; fixTwo <= len - 3;)
            {
                long newTarget = (long)target - (nums[fixOne] + nums[fixTwo]);
                //单次双固定的寻找
                for (int left = fixTwo + 1, right = len - 1; left < right;)
                {
                    //  cout << "fixOne:" << fixOne << " fixTwo:" << fixTwo << " left: " << left << " right:" << right << endl;
                    if (nums[left] + nums[right] < newTarget)left++;
                    else if (nums[left] + nums[right] > newTarget)right--;
                    else
                    {
                        //  cout << "success: fixOne:" << fixOne << " fixTwo:" << fixTwo << " left: " << left << " right:" << right << endl;                      
                        ret.push_back({ nums[fixOne],nums[fixTwo],nums[left],nums[right] });
                        left++, right--;

                        //非固定去重
                        while (left < right && nums[left] == nums[left - 1])left++;
                        while (left < right && nums[right] == nums[right + 1])right--;
                    }
                }
                ++fixTwo;
                //固定去重
                while (fixTwo <= len - 3 && nums[fixTwo] == nums[fixTwo - 1])fixTwo++;
            }

            ++fixOne;
            //固定去重
            while (fixOne <= len - 4 && nums[fixOne] == nums[fixOne - 1])fixOne++;
        }
        return ret;
    }
};

//答案
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 利⽤ 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim) right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left++],
                        nums[right--] });
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};